#include "manifest.h"

static int64 REMOVED = -1;

typedef struct {
    int capacity;
    int size;
    int* hashes;
    int64* values;
    int64* keys;
} _mapll_t;

static bool mapll_put_hashed(mapll_t m, int64 k, int64 v, int hash);
static void mapll_dispose_innards(mapll_t m);

mapll_t mapll_create(int capacity) {
    capacity = capacity < 16 ? 16 : capacity;
    _mapll_t* map = mem_allocz(sizeof(_mapll_t));
    if (map != null) {
        map->keys = (int64*)mem_allocz(capacity * sizeof(int64));
        map->values = (int64*)mem_allocz(capacity * sizeof(int64));
        map->hashes = (int*)mem_allocz(capacity * sizeof(int));
        map->capacity = capacity;
        if (map->keys == null || map->values == null || map->hashes == null) {
            mapll_dispose(map);
            map = null;
        }
    }
    return map;
}

int mapll_size(mapll_t m) {
    _mapll_t* map = (_mapll_t*)m;
    return map->size;
}

static int hash0(int64 k) {
    unsigned int h = (unsigned int)k ^ (unsigned int)(((unsigned int64)k) >> 32);
    /* Doug Lea's supplemental secondaryHash function */
    h ^= (h >> 20) ^ (h >> 12);
    h ^= (h >> 7) ^ (h >> 4);
    return (int)(h & 0x7FFFFFFF);
}

static bool mapll_grow(mapll_t m) {
    _mapll_t* m1 = (_mapll_t*)m;
    int c = m1->capacity;
    _mapll_t* m2 = (_mapll_t*)mapll_create(c * 3 / 2);
    if (m2 != null) {
        assertion(m2 != null, "out of memory");
        int i = 0;
        while (i < c) {
            if (m1->keys[i] != null && m1->keys[i] != REMOVED) {
                bool b = mapll_put_hashed(m2, m1->keys[i], m1->values[i], m1->hashes[i]);
                if (!b) {
                    mapll_dispose(m2);
                    return false;
                }
                m1->keys[i] = null;
            }
            i++;
        }
    }
    assert(m2->size == m1->size);
    mapll_dispose_innards(m1);
    m1->keys = m2->keys;
    m1->values = m2->values;
    m1->hashes = m2->hashes;
    m1->capacity = m2->capacity;
    m2->keys = null;
    m2->values = null;
    m2->hashes = null;
    mapll_dispose(m2);
    return true;
}

bool mapll_put(mapll_t m, int64 k, int64 v) {
    assertion(v != 0 && k > 0, "expected k > 0 k=%lld v=%lld", k, v);
    _mapll_t* map = (_mapll_t*)m;
    if (v == 0 || k == 0) {
        return false;
    } else {
        int hash = hash0(k);
        bool b = mapll_put_hashed(m, k, v, hash);
        b = b || (mapll_grow(m) && mapll_put_hashed(m, k, v, hash));
        return b;
    }
}

static bool mapll_put_hashed(mapll_t m, int64 k, int64 v, int hash) {
    assertion(k > 0, "only keys > 0 are supported k=%lld v=%lld", k, v);
    _mapll_t* map = (_mapll_t*)m;
    int h = hash % map->capacity;
    int h0 = h;
    for (;;) {
        if (map->keys[h] == 0 || map->keys[h] == k || map->keys[h] == REMOVED) {
            break;
        }
        h = (h + 1) % map->capacity;
        if (h == h0) {
            return false; /* need to grow */
        }
    }
    if (map->keys[h] == 0 || map->keys[h] == REMOVED) {
        map->keys[h] = k;
        map->hashes[h] = hash;
        map->size++;
    }
    map->values[h] = v;
    return true;
}

int64 mapll_get(mapll_t m, int64 k) {
    _mapll_t* map = (_mapll_t*)m;
    int hash = hash0(k);
    int h = hash % map->capacity;
    int h0 = h;
    for (;;) {
        if (map->keys[h] == 0) {
            return 0;
        }
        if (map->keys[h] == k) {
            return map->values[h];
        }
        h = (h + 1) % map->capacity;
        if (h == h0) {
            return 0;
        }
    }
}

int64 mapll_remove(mapll_t m, int64 k) {
    assert(k > 0);
    _mapll_t* map = (_mapll_t*)m;
    int hash = hash0(k);
    int h = hash % map->capacity;
    int h0 = h;
    for (;;) {
        if (map->keys[h] == 0) {
            return 0;
        }
        if (map->keys[h] == k) {
            map->keys[h] = REMOVED;
            map->hashes[h] = 0;
            map->size--;
            return map->values[h];
        }
        h = (h + 1) % map->capacity;
        if (h == h0) {
            return 0;
        }
    }
}

void mapll_foreach(mapll_t m, void (*each)(mapll_t, int64, void* rt), void* rt) {
    _mapll_t* map = (_mapll_t*)m;
    for (int i = 0; i < map->capacity; i++) {
        if (map->keys[i] != 0) {
            each(m, map->keys[i], rt);
        }
    }
}

void mapll_clear(mapll_t m) {
    _mapll_t* map = (_mapll_t*)m;
    assert(map != null);
    if (map != null) {
        if (map->keys != null) {
            for (int i = 0; i < map->capacity; i++) {
                map->keys[i] = 0;
                map->values[i] = 0;
                map->hashes[i] = 0;
            }
        }
        map->size = 0;
    }
}

static void mapll_dispose_innards(mapll_t m) {
    _mapll_t* map = (_mapll_t*)m;
    if (map != null) {
        if (map->keys != null) {
            mem_free(map->keys);
            map->keys = null;
        }
        if (map->values != null) {
            mem_free(map->values);
            map->values = null;
        }
        if (map->hashes != null) {
            mem_free(map->hashes);
            map->hashes = null;
        }
    }
}

void mapll_dispose(mapll_t m) {
    _mapll_t* map = (_mapll_t*)m;
    if (map != null) {
        mapll_dispose_innards(m);
        mem_free(map);
    }
}

/* smoke test */

static void fill_map(mapll_t m, int64* keys, int N) {
    for (int i = 0; i < N; i++) {
        int64 key = keys[i];
        int size = mapll_size(m);
        mapll_put(m, key, i + 1);
        assertion(size + 1 == mapll_size(m), "expected %d instead of %d", size + 1, mapll_size(m));
        assertion(i + 1 == mapll_size(m), "expected %d instead of %d", i + 1, mapll_size(m));
        int64 v = mapll_get(m, key);
        assertion(i + 1 == v, "expected %d mapll_get(%s)=%lld", i+1, key, v);
        assert(v == i + 1);
    }
    assert(mapll_size(m) == N);
}

static void each(mapll_t m, int64 key, void* extra) {
    int64* keys = (int64*)extra;
    int size = mapll_size(m);
    bool found = false;
    for (int i = 0; i < size && !found; i++) {
        found = key == keys[i];
    }
    assert(found);
}

static void remove_each(mapll_t m, int64 key, void* unused) {
    mapll_remove(m, key);
}

void mapll_smoke_test(bool single_thread) {
    int64 ad = mem_allocated();
    int64 as = mem_allocations();
    const int N = 1000;
    int64 keys[N];
    for (int i = 0; i < N; i++) {
        int64 k = (i + 1) + ((int64)rand() << 28);
        while (k <= 0) {
            k = (i + 1) + ((int64)rand() << 28);
        }
        keys[i] = k;
    }
    mapll_t m = mapll_create(1);
    fill_map(m, keys, N);
    mapll_dispose(m);

    m = mapll_create(1);
    fill_map(m, keys, N);
    for (int i = 0; i < N; i++) {
        int64 key = keys[i];
        int size = mapll_size(m);
        mapll_remove(m, key);
        assertion(size - 1 == mapll_size(m), "expected %d instead of %d", size - 1, mapll_size(m));
        int64 v = mapll_get(m, key);
        assertion(v == 0, "mapll_get(%s)=%lld instead of 0", key, v);
    }
    assert(mapll_size(m) == 0);
    mapll_dispose(m);

    m = mapll_create(1);
    fill_map(m, keys, N);
    mapll_clear(m);
    assert(mapll_size(m) == 0);
    mapll_dispose(m);

    m = mapll_create(1);
    fill_map(m, keys, N);
    mapll_foreach(m, each, keys);
    mapll_foreach(m, remove_each, keys);
    assert(mapll_size(m) == 0);
    mapll_dispose(m);

    if (single_thread) {
        assertion(ad == mem_allocated() && as == mem_allocations(),
                 "ad=%lld mem_allocated()=%lld as=%lld mem_allocates()=%lld",
                  ad, mem_allocated(), as, mem_allocations());
    }
}

